#include <iostream>
#include "incrSubArray.h"

using namespace std;

bool incrSubArray(int *array, int elem_num, int *sub_array, int &sub_elem_num) {
    if (array == NULL ||
        elem_num <= 0) {
        cout << "Invalid argument!" << endl;
        return false;
    }

    sub_elem_num = 0;
    int *p = new int[elem_num];
    if (p == NULL) {
        cout << "Allocate index buffer error!" << endl;
        return false;
    }

    int *m = new int[elem_num + 1];
    if (m == NULL) {
        cout << "Allocate m buffer error!" << endl;
        return false;
    }

    sub_elem_num = 1;
    p[0] = -1;
    m[0] = 0;

    int i, sub_i, new_l;
    for (i = 1; i < elem_num; i++) {
        for (sub_i = 0; sub_i < sub_elem_num; sub_i++) {
            if (array[i] < array[m[sub_i]]) {
                break;
            }
        }

        p[i] = m[sub_i - 1];

        // array[i] is smaller than some previous number
        if (sub_i >= sub_elem_num) {
            m[sub_i] = i;
            sub_elem_num++;
        }
        else if (array[i] < array[m[sub_i]]) {
            m[sub_i] = i;
        }
    }

    sub_i = m[sub_elem_num-1];
    for (i = sub_elem_num - 1; i >= 0; --i) {
        sub_array[i] = array[sub_i];
        sub_i = p[sub_i];
    }

    delete m;
    delete p;

    return true;
}

bool incrSubArrayLog(int *array, int elem_num, int *sub_array, int &sub_elem_num) {
    if (array == NULL ||
        elem_num <= 0) {
        cout << "Invalid argument!" << endl;
        return false;
    }

    sub_elem_num = 0;
    int *p = new int[elem_num];
    if (p == NULL) {
        cout << "Allocate index buffer error!" << endl;
        return false;
    }

    int *m = new int[elem_num + 1];
    if (m == NULL) {
        cout << "Allocate m buffer error!" << endl;
        return false;
    }

    sub_elem_num = 1;
    p[0] = -1;
    m[0] = 0;

    int i, sub_i, new_l;
    for (i = 1; i < elem_num; i++) {
        int l = 0;
        int r = sub_elem_num;

        while (l < r) {
            int mid_loc = (l + r) / 2;
            if  (array[i] == array[m[mid_loc]]) {
                l = mid_loc;
                break;
            }
            else if (array[i] < array[m[mid_loc]]) {
                r = mid_loc - 1;
            }
            else {
                l = mid_loc + 1;
            }
        }

        sub_i = l;

        p[i] = m[sub_i - 1];

        // array[i] is smaller than some previous number
        if (sub_i >= sub_elem_num) {
            m[sub_i] = i;
            sub_elem_num++;
        }
        else if (array[i] < array[m[sub_i]]) {
            m[sub_i] = i;
        }
    }

    sub_i = m[sub_elem_num-1];
    for (i = sub_elem_num - 1; i >= 0; --i) {
        sub_array[i] = array[sub_i];
        sub_i = p[sub_i];
    }

    delete m;
    delete p;

    return true;
}

